The present invention relates to methods of transmitting “continuous media programs” such as video or audio files to multiple consumers at arbitrary starting times as selected by consumers within a delivery period. In particular, the present invention provides a method of reducing the bandwidth that must be reserved to transmit such data.
“Continuous media programs” present data that a consumer will normally process sequentially on a real-time basis. Examples of continuous media programs are video and audio programs, including movies, television shows, news clips, product advertisements, medical or recreational information or educational programs. This list of examples is not exhaustive.
“On-demand delivery” of a continuous media program is the delivery of the program beginning at a starting time occurring substantially at the time a consumer requests the program. For example, in a video-on-demand (VOD) system, a customer might be able to request viewing of a video program at a starting times every five minutes over the course of a several hour delivery period.
In order to reduce the costs of storage and distribution, continuous media programs may be multicast from a central server to a large number of consumers via phone lines, cable systems, broadcast radio, satellite links or other methods. For popular programs, many new requests will arrive at the central server during a delivery period. In response to these requests, the server may make a separate transmission of data to each consumer. This approach is simple and works with standard receiving devices (e.g., television sets) but has the disadvantage of requiring a large number of transmission channels, one for each starting time where a request has been received. For this simple scheme, the bandwidth (e.g., number of channels) required to serve requests increases linearly with the number of starting times required and thus does not scale well to large numbers of starting times where requests will be received.
One method of reducing the bandwidth required for supporting on-demand transmissions of continuous media programs divides the program into a number of segments each assigned to a different channel, for example, a conventional cable channel (using frequency multiplexing) or a logical channel such as may be achieved using different Internet addresses or the like. The segments are of increasing length and each segment is transmitted repetitively on its channel. Thus, for example, a first channel may repeatedly transmit a segment consisting of the first one minute of the program while a second, third, and fourth channel may repeatedly transmit minutes two and three, four and five, and six through nine, respectively.
Under this system, a consumer wishing to receive a program waits until the next starting time upon which, the consumer's receiver connects to the first channel to receive and play the first minute of program from that channel. At the end of the first minute, the receiver automatically switches to the second channel and so forth.
In the case where two channels do not begin and end to permit a clean switchover, for example, if the first and second channels begin their segments at the same time, the receiver records (buffers) the data of the later channel to be played back when the earlier channel is completed. Using properly arranged and sized segments, the receiver can switch channels to assemble different segments of the program into a continuous program thread that may be viewed without interruption by the consumer. This method is termed “skyscrapering” referring generally to how the segments of the program thread, when stacked like blocks from smallest to largest, resemble the profile of a skyscraper.
As can be seen from this simple example, four channels are sufficient to transmit a nine-minute program starting every minute. If separate broadcasts (and channels) were required for each new start time, nine channels would be needed. Skyscrapering thus reduces the bandwidth required for regular transmissions without loss of fidelity or other distortions of the program.
When multiple programs must be delivered, a variation on the skyscrapering system termed “dynamic skyscrapering” may be used to provide even greater transmission efficiencies. Dynamic skyscrapering recognizes that the segments distributed among different channels for a given program may be organized into clusters linking all segments on all channels that may form a complete program thread with a given segment of the final channel of the program. The boundary of a cluster exhibits the general merging that occurs in skyscrapering where many initial multicasts of data at starting times ultimately merge to a single stream represented by the final segment in the final channel of the transmission.
A significance of clusters is that once a first segment in a first channel of a cluster is requested, later requests for start times within the cluster do not require additional delivery of the final segment. Thus each cluster represents a single complete showing of the continuous media program and the next cluster represents a new showing.
Dynamic skyscrapering recognizes that at the interface between clusters, program material may be readily changed and exploits this fact when multiple programs are being transmitted, by sharing uncommitted clusters between programs. Specifically, a number of channels are collected into channel blocks each dedicated to a continuous media program. The clusters in the different blocks may be staggered in starting times. As requests for particular programs come in, they are assigned on a first-come, first-serve basis, first to any existing cluster currently transmitting the desired program and, if there are none, to any available cluster that has not previously been assigned. In this way, clusters not used for a given program because of lack of requests during the cluster time can be reassigned to another program. The staggering maximizes the availability of unassigned clusters and reduces the average waiting time when clusters are not available.
Early segments of a cluster that has already been assigned to a program may be shared with programs of different blocks (“channel stealing”) to shorten the waiting time for a given program. However, extensive sharing of individual segments is not possible because merging causes conflicts at later segments in the cluster allocated to previous and later program threads.